<head><meta charset="UTF-8"></head><h1 class="heading">InnoDB数据页结构</h1>
<p>标签： MySQL是怎样运行的</p>
<hr>
<h2 class="heading">不同类型的页简介</h2>
<p>前边我们简单提了一下<code>页</code>的概念，它是<code>InnoDB</code>管理存储空间的基本单位，一个页的大小一般是<code>16KB</code>。<code>InnoDB</code>为了不同的目的而设计了许多种不同类型的<code>页</code>，比如存放表空间头部信息的页，存放<code>Insert Buffer</code>信息的页，存放<code>INODE</code>信息的页，存放<code>undo</code>日志信息的页等等等等。当然了，如果我说的这些名词你一个都没有听过，就当我放了个屁吧～ 不过这没有一毛钱关系，我们今儿个也不准备说这些类型的页，我们聚焦的是那些存放我们表中记录的那种类型的页，官方称这种存放记录的页为索引（<code>INDEX</code>）页，鉴于我们还没有了解过索引是个什么东西，而这些表中的记录就是我们日常口中所称的<code>数据</code>，所以目前还是叫这种存放记录的页为<code>数据页</code>吧。</p>
<h2 class="heading">数据页结构的快速浏览</h2>
<p>数据页代表的这块<code>16KB</code>大小的存储空间可以被划分为多个部分，不同部分有不同的功能，各个部分如图所示：</p>
<p></p><figure><img alt="image_1d5g808sn1bmg2861d5b1b32lht19.png-77.5kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c0ff3068b29?w=499&amp;h=551&amp;f=png&amp;s=79402"><figcaption></figcaption></figure><p></p>
<p>从图中可以看出，一个<code>InnoDB</code>数据页的存储空间大致被划分成了<code>7</code>个部分，有的部分占用的字节数是确定的，有的部分占用的字节数是不确定的。下边我们用表格的方式来大致描述一下这7个部分都存储一些啥内容（快速的瞅一眼就行了，后边会详细唠叨的）：</p>
<table>
<thead>
<tr>
<th style="text-align:center">名称</th>
<th style="text-align:center">中文名</th>
<th style="text-align:center">占用空间大小</th>
<th style="text-align:center">简单描述</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"><code>File Header</code></td>
<td style="text-align:center">文件头部</td>
<td style="text-align:center"><code>38</code>字节</td>
<td style="text-align:center">页的一些通用信息</td>
</tr>
<tr>
<td style="text-align:center"><code>Page Header</code></td>
<td style="text-align:center">页面头部</td>
<td style="text-align:center"><code>56</code>字节</td>
<td style="text-align:center">数据页专有的一些信息</td>
</tr>
<tr>
<td style="text-align:center"><code>Infimum + Supremum</code></td>
<td style="text-align:center">最小记录和最大记录</td>
<td style="text-align:center"><code>26</code>字节</td>
<td style="text-align:center">两个虚拟的行记录</td>
</tr>
<tr>
<td style="text-align:center"><code>User Records</code></td>
<td style="text-align:center">用户记录</td>
<td style="text-align:center">不确定</td>
<td style="text-align:center">实际存储的行记录内容</td>
</tr>
<tr>
<td style="text-align:center"><code>Free Space</code></td>
<td style="text-align:center">空闲空间</td>
<td style="text-align:center">不确定</td>
<td style="text-align:center">页中尚未使用的空间</td>
</tr>
<tr>
<td style="text-align:center"><code>Page Directory</code></td>
<td style="text-align:center">页面目录</td>
<td style="text-align:center">不确定</td>
<td style="text-align:center">页中的某些记录的相对位置</td>
</tr>
<tr>
<td style="text-align:center"><code>File Trailer</code></td>
<td style="text-align:center">文件尾部</td>
<td style="text-align:center"><code>8</code>字节</td>
<td style="text-align:center">校验页是否完整</td>
</tr>
</tbody>
</table>
<blockquote class="warning"><p>小贴士：

我们接下来并不打算按照页中各个部分的出现顺序来依次介绍它们，因为各个部分中会出现很多大家目前不理解的概念，这会打击各位读文章的信心与兴趣，希望各位能接受这种拍摄手法～
</p></blockquote><h2 class="heading">记录在页中的存储</h2>
<p>在页的7个组成部分中，我们自己存储的记录会按照我们指定的<code>行格式</code>存储到<code>User Records</code>部分。但是在一开始生成页的时候，其实并没有<code>User Records</code>这个部分，每当我们插入一条记录，都会从<code>Free Space</code>部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到<code>User Records</code>部分，当<code>Free Space</code>部分的空间全部被<code>User Records</code>部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了，这个过程的图示如下：</p>
<p></p><figure><img alt="image_1cosvi1in9st476cdqfki1n39m.png-133.8kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c0fe86555ed?w=1272&amp;h=475&amp;f=png&amp;s=137021"><figcaption></figcaption></figure><p></p>
<p>为了更好的管理在<code>User Records</code>中的这些记录，<code>InnoDB</code>可费了一番力气呢，在哪费力气了呢？不就是把记录按照指定的行格式一条一条摆在<code>User Records</code>部分么？其实这话还得从记录行格式的<code>记录头信息</code>中说起。</p>
<h3 class="heading">记录头信息的秘密</h3>
<p>为了故事的顺利发展，我们先创建一个表：</p>
<pre><code class="hljs bash" lang="bash">mysql&gt; CREATE TABLE page_demo(
    -&gt;     c1 INT,
    -&gt;     c2 INT,
    -&gt;     c3 VARCHAR(10000),
    -&gt;     PRIMARY KEY (c1)
    -&gt; ) CHARSET=ascii ROW_FORMAT=Compact;
Query OK, 0 rows affected (0.03 sec)
</code></pre><p>这个新创建的<code>page_demo</code>表有3个列，其中<code>c1</code>和<code>c2</code>列是用来存储整数的，<code>c3</code>列是用来存储字符串的。需要注意的是，<span style="color:red">我们把 <em><strong>c1</strong></em> 列指定为主键，所以在具体的行格式中InnoDB就没必要为我们去创建那个所谓的 <em><strong>row_id</strong></em> 隐藏列了</span>。而且我们为这个表指定了<code>ascii</code>字符集以及<code>Compact</code>的行格式。所以这个表中记录的行格式示意图就是这样的：</p>
<p></p><figure><img alt="image_1c9o2eib2vl11qnf1dfl1d2lco313.png-76.4kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c0feca77be3?w=1121&amp;h=474&amp;f=png&amp;s=78271"><figcaption></figcaption></figure><p></p>
<p>从图中可以看到，我们特意把<code>记录头信息</code>的5个字节的数据给标出来了，说明它很重要，我们再次先把这些<code>记录头信息</code>中各个属性的大体意思浏览一下（我们目前使用<code>Compact</code>行格式进行演示）：</p>
<table>
<thead>
<tr>
<th style="text-align:center">名称</th>
<th style="text-align:center">大小（单位：bit）</th>
<th style="text-align:center">描述</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"><code>预留位1</code></td>
<td style="text-align:center"><code>1</code></td>
<td style="text-align:center">没有使用</td>
</tr>
<tr>
<td style="text-align:center"><code>预留位2</code></td>
<td style="text-align:center"><code>1</code></td>
<td style="text-align:center">没有使用</td>
</tr>
<tr>
<td style="text-align:center"><code>delete_mask</code></td>
<td style="text-align:center"><code>1</code></td>
<td style="text-align:center">标记该记录是否被删除</td>
</tr>
<tr>
<td style="text-align:center"><code>min_rec_mask</code></td>
<td style="text-align:center"><code>1</code></td>
<td style="text-align:center">B+树的每层非叶子节点中的最小记录都会添加该标记</td>
</tr>
<tr>
<td style="text-align:center"><code>n_owned</code></td>
<td style="text-align:center"><code>4</code></td>
<td style="text-align:center">表示当前记录拥有的记录数</td>
</tr>
<tr>
<td style="text-align:center"><code>heap_no</code></td>
<td style="text-align:center"><code>13</code></td>
<td style="text-align:center">表示当前记录在记录堆的位置信息</td>
</tr>
<tr>
<td style="text-align:center"><code>record_type</code></td>
<td style="text-align:center"><code>3</code></td>
<td style="text-align:center">表示当前记录的类型，<code>0</code>表示普通记录，<code>1</code>表示B+树非叶节点记录，<code>2</code>表示最小记录，<code>3</code>表示最大记录</td>
</tr>
<tr>
<td style="text-align:center"><code>next_record</code></td>
<td style="text-align:center"><code>16</code></td>
<td style="text-align:center">表示下一条记录的相对位置</td>
</tr>
</tbody>
</table>
<p>由于我们现在主要在唠叨<code>记录头信息</code>的作用，所以为了大家理解上的方便，我们只在<code>page_demo</code>表的行格式演示图中画出有关的头信息属性以及<code>c1</code>、<code>c2</code>、<code>c3</code>列的信息（其他信息没画不代表它们不存在啊，只是为了理解上的方便在图中省略了～），简化后的行格式示意图就是这样：</p>
<p></p><figure><img alt="image_1c9o52lt41v5c7vk1vm91fsm174b2d.png-49.5kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c0ff1ae5364?w=759&amp;h=347&amp;f=png&amp;s=50721"><figcaption></figcaption></figure><p></p>
<p>下边我们试着向<code>page_demo</code>表中插入几条记录：</p>
<pre><code class="hljs bash" lang="bash">mysql&gt; INSERT INTO page_demo VALUES(1, 100, <span class="hljs-string">'aaaa'</span>), (2, 200, <span class="hljs-string">'bbbb'</span>), (3, 300, <span class="hljs-string">'cccc'</span>), (4, 400, <span class="hljs-string">'dddd'</span>);
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0
</code></pre><p>为了方便大家分析这些记录在<code>页</code>的<code>User Records</code>部分中是怎么表示的，我把记录中头信息和实际的列数据都用十进制表示出来了（其实是一堆二进制位），所以这些记录的示意图就是：</p>
<p></p><figure><img alt="image_1c9qs0j281knc16hc1hqsgj01v0o2c.png-82.8kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c0ff83f9870?w=948&amp;h=333&amp;f=png&amp;s=84803"><figcaption></figcaption></figure><p></p>
<p>看这个图的时候需要注意一下，各条记录在<code>User Records</code>中存储的时候并没有空隙，这里只是为了大家观看方便才把每条记录单独画在一行中。我们对照着这个图来看看记录头信息中的各个属性是啥意思：</p>
<ul>
<li>
<p><code>delete_mask</code></p>
<p>这个属性标记着当前记录是否被删除，占用1个二进制位，值为<code>0</code>的时候代表记录并没有被删除，为<code>1</code>的时候代表记录被删除掉了。</p>
<p>啥？被删除的记录还在<code>页</code>中么？是的，摆在台面上的和背地里做的可能大相径庭，你以为它删除了，可它还在真实的磁盘上[摊手]（忽然想起冠希～）。这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗，所以只是打一个删除标记而已，所有被删除掉的记录都会组成一个所谓的<code>垃圾链表</code>，在这个链表中的记录占用的空间称之为所谓的<code>可重用空间</code>，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。</p>
<blockquote class="warning"><p>小贴士：

将这个delete_mask位设置为1和将被删除的记录加入到垃圾链表中其实是两个阶段，我们后边在介绍事务的时候会详细唠叨删除操作的详细过程，稍安勿躁。
</p></blockquote></li>
<li>
<p><code>min_rec_mask</code></p>
<p>B+树的每层非叶子节点中的最小记录都会添加该标记，什么是个<code>B+</code>树？什么是个非叶子节点？好吧，等会再聊这个问题。反正我们自己插入的四条记录的<code>min_rec_mask</code>值都是<code>0</code>，意味着它们都不是<code>B+</code>树的非叶子节点中的最小记录。</p>
</li>
<li>
<p><code>n_owned</code></p>
<p>这个暂时保密，稍后它是主角～</p>
</li>
<li>
<p><code>heap_no</code></p>
<p>这个属性表示当前记录在本<code>页</code>中的位置，从图中可以看出来，我们插入的4条记录在本<code>页</code>中的位置分别是：<code>2</code>、<code>3</code>、<code>4</code>、<code>5</code>。是不是少了点啥？是的，怎么不见<code>heap_no</code>值为<code>0</code>和<code>1</code>的记录呢？</p>
<p>这其实是设计<code>InnoDB</code>的大叔们玩的一个小把戏，他们自动给每个页里边儿加了两个记录，由于这两个记录并不是我们自己插入的，所以有时候也称为<code>伪记录</code>或者<code>虚拟记录</code>。这两个伪记录一个代表<code>最小记录</code>，一个代表<code>最大记录</code>，等一下哈~，记录可以比大小么？</p>
<p>是的，记录也可以比大小，对于<span style="color:red">一条完整的记录</span>来说，比较记录的大小就是比较<code>主键</code>的大小。比方说我们插入的4行记录的主键值分别是：<code>1</code>、<code>2</code>、<code>3</code>、<code>4</code>，这也就意味着这4条记录的大小从小到大依次递增。</p>
<blockquote class="warning"><p>小贴士：

请注意我强调了对于`一条完整的记录`来说，比较记录的大小就相当于比的是主键的大小。后边我们还会介绍只存储一条记录的部分列的情况，敬请期待～
</p></blockquote><p>但是不管我们向<code>页</code>中插入了多少自己的记录，设计<code>InnoDB</code>的大叔们都规定他们定义的两条伪记录分别为最小记录与最大记录。这两条记录的构造十分简单，都是由5字节大小的<code>记录头信息</code>和8字节大小的一个固定的部分组成的，如图所示</p>
<p></p><figure><img alt="image_1c9ra45eam7t1mil9o1h3ucqdhv.png-50.4kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c100ff0ccc2?w=576&amp;h=395&amp;f=png&amp;s=51648"><figcaption></figcaption></figure><p></p>
<p>由于这两条记录不是我们自己定义的记录，所以它们并不存放在<code>页</code>的<code>User Records</code>部分，他们被单独放在一个称为<code>Infimum + Supremum</code>的部分，如图所示：</p>
<p></p><figure><img alt="image_1c9qs1mn2t3j1nt344116nk15uf2p.png-119.7kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c10773d8cee"><figcaption></figcaption></figure><p></p>
<p>从图中我们可以看出来，最小记录和最大记录的<code>heap_no</code>值分别是<code>0</code>和<code>1</code>，也就是说它们的位置最靠前。</p>
</li>
<li>
<p><code>record_type</code></p>
<p>这个属性表示当前记录的类型，一共有4种类型的记录，<code>0</code>表示普通记录，<code>1</code>表示B+树非叶节点记录，<code>2</code>表示最小记录，<code>3</code>表示最大记录。从图中我们也可以看出来，我们自己插入的记录就是普通记录，它们的<code>record_type</code>值都是<code>0</code>，而最小记录和最大记录的<code>record_type</code>值分别为<code>2</code>和<code>3</code>。</p>
<p>至于<code>record_type</code>为<code>1</code>的情况，我们之后在说索引的时候会重点强调的。</p>
</li>
<li>
<p><code>next_record</code></p>
<p>这玩意儿非常重要，它表示<span style="color:red">从当前记录的真实数据到下一条记录的真实数据的地址偏移量</span>。比方说第一条记录的<code>next_record</code>值为<code>32</code>，意味着从第一条记录的真实数据的地址处向后找<code>32</code>个字节便是下一条记录的真实数据。如果你熟悉数据结构的话，就立即明白了，这其实是个<code>链表</code>，可以通过一条记录找到它的下一条记录。但是需要注意注意再注意的一点是，<span style="color:red"><code>下一条记录</code>指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录</span>。而且规定<span style="color:red"> <em><strong>Infimum记录（也就是最小记录）</strong></em> 的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是 <em><strong>Supremum记录（也就是最大记录）</strong></em>  </span>，为了更形象的表示一下这个<code>next_record</code>起到的作用，我们用箭头来替代一下<code>next_record</code>中的地址偏移量：</p>
<p></p><figure><img alt="image_1cot1r96210ph1jng1td41ouj85c13.png-120.5kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c1084c440b4?w=1044&amp;h=549&amp;f=png&amp;s=123443"><figcaption></figcaption></figure><p></p>
<p>从图中可以看出来，<span style="color:red">我们的记录按照主键从小到大的顺序形成了一个单链表</span>。<code>最大记录</code>的<code>next_record</code>的值为<code>0</code>，这也就是说最大记录是没有<code>下一条记录</code>了，它是这个单链表中的最后一个节点。如果从中删除掉一条记录，这个链表也是会跟着变化的，比如我们把第2条记录删掉：</p>
<pre><code class="hljs bash" lang="bash">mysql&gt; DELETE FROM page_demo WHERE c1 = 2;
Query OK, 1 row affected (0.02 sec)
</code></pre><p>删掉第2条记录后的示意图就是：</p>
<p></p><figure><img alt="image_1cul8slbp1om0p31b3u1be11gco9.png-119.6kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c108ee1da43?w=1032&amp;h=528&amp;f=png&amp;s=122514"><figcaption></figcaption></figure><p></p>
<p>从图中可以看出来，删除第2条记录前后主要发生了这些变化：</p>
<ul>
<li>第2条记录并没有从存储空间中移除，而是把该条记录的<code>delete_mask</code>值设置为<code>1</code>。</li>
<li>第2条记录的<code>next_record</code>值变为了0，意味着该记录没有下一条记录了。</li>
<li>第1条记录的<code>next_record</code>指向了第3条记录。</li>
<li>还有一点你可能忽略了，就是<code>最大记录</code>的<code>n_owned</code>值从<code>5</code>变成了<code>4</code>，关于这一点的变化我们稍后会详细说明的。</li>
</ul>
<p>所以，<span style="color:red">不论我们怎么对页中的记录做增删改操作，InnoDB始终会维护一条记录的单链表，链表中的各个节点是按照主键值由小到大的顺序连接起来的</span>。</p>
<blockquote class="warning"><p>小贴士：

你会不会觉得next_record这个指针有点儿怪，为啥要指向记录头信息和真实数据之间的位置呢？为啥不干脆指向整条记录的开头位置，也就是记录的额外信息开头的位置呢？

因为这个位置刚刚好，向左读取就是记录头信息，向右读取就是真实数据。我们前边还说过变长字段长度列表、NULL值列表中的信息都是逆序存放，这样可以使记录中位置靠前的字段和它们对应的字段长度信息在内存中的距离更近，可能会提高高速缓存的命中率。当然如果你看不懂这句话的话就不要勉强了，果断跳过～
</p></blockquote></li>
</ul>
<p>再来看一个有意思的事情，因为主键值为<code>2</code>的记录被我们删掉了，但是存储空间却没有回收，如果我们再次把这条记录插入到表中，会发生什么事呢？</p>
<pre><code class="hljs bash" lang="bash">mysql&gt; INSERT INTO page_demo VALUES(2, 200, <span class="hljs-string">'bbbb'</span>);
Query OK, 1 row affected (0.00 sec)
</code></pre><p>我们看一下记录的存储情况：</p>
<p></p><figure><img alt="image_1cot2j9n94a511jd15clrrfp6p1t.png-137.8kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c109f25d55d?w=1120&amp;h=557&amp;f=png&amp;s=141111"><figcaption></figcaption></figure><p></p>
<p>从图中可以看到，<code>InnoDB</code>并没有因为新记录的插入而为它申请新的存储空间，而是直接复用了原来被删除记录的存储空间。</p>
<blockquote class="warning"><p>小贴士：

当数据页中存在多条被删除掉的记录时，这些记录的next_record属性将会把这些被删除掉的记录组成一个垃圾链表，以备之后重用这部分存储空间。
</p></blockquote><h2 class="heading">Page Directory（页目录）</h2>
<p>现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表，那如果我们想根据主键值查找页中的某条记录该咋办呢？比如说这样的查询语句：</p>
<pre><code class="hljs bash" lang="bash">SELECT * FROM page_demo WHERE c1 = 3;
</code></pre><p>最笨的办法：从<code>Infimum</code>记录（最小记录）开始，沿着链表一直往后找，总有一天会找到（或者找不到[摊手]），在找的时候还能投机取巧，因为链表中各个记录的值是按照从小到大顺序排列的，所以当链表的某个节点代表的记录的主键值大于你想要查找的主键值时，你就可以停止查找了，因为该节点后边的节点的主键值依次递增。</p>
<p>这个方法在页中存储的记录数量比较少的情况用起来也没啥问题，比方说现在我们的表里只有<code>4</code>条自己插入的记录，所以最多找<code>4</code>次就可以把所有记录都遍历一遍，但是如果一个页中存储了非常多的记录，这么查找对性能来说还是有损耗的，所以我们说这种遍历查找这是一个<code>笨</code>办法。但是设计<code>InnoDB</code>的大叔们是什么人，他们能用这么笨的办法么，当然是要设计一种更6的查找方式喽，他们从书的目录中找到了灵感。</p>
<p>我们平常想从一本书中查找某个内容的时候，一般会先看目录，找到需要查找的内容对应的书的页码，然后到对应的页码查看内容。设计<code>InnoDB</code>的大叔们为我们的记录也制作了一个类似的目录，他们的制作过程是这样的：</p>
<ol>
<li>
<p>将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。</p>
</li>
<li>
<p>每个组的<span style="color:red">最后</span>一条记录（也就是组内最大的那条记录）的头信息中的<code>n_owned</code>属性表示该记录拥有多少条记录，也就是该组内共有几条记录。</p>
</li>
<li>
<p>将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近<code>页</code>的尾部的地方，这个地方就是所谓的<code>Page Directory</code>，也就是<code>页目录</code>（此时应该返回头看看页面各个部分的图）。页面目录中的这些地址偏移量被称为<code>槽</code>（英文名：<code>Slot</code>），所以这个页面目录就是由<code>槽</code>组成的。</p>
</li>
</ol>
<p>比方说现在的<code>page_demo</code>表中正常的记录共有6条，<code>InnoDB</code>会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录，看下边的示意图：</p>
<p></p><figure><img alt="image_1couapvdmb5mvm1i0l5m0vcb2a.png-128.2kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c10c57164a6?w=1011&amp;h=540&amp;f=png&amp;s=131292"><figcaption></figcaption></figure><p></p>
<p>从这个图中我们需要注意这么几点：</p>
<ul>
<li>
<p>现在<code>页目录</code>部分中有两个槽，也就意味着我们的记录被分成了两个组，<code>槽1</code>中的值是<code>112</code>，代表最大记录的地址偏移量（就是从页面的0字节开始数，数112个字节）；<code>槽0</code>中的值是<code>99</code>，代表最小记录的地址偏移量。</p>
</li>
<li>
<p>注意最小和最大记录的头信息中的<code>n_owned</code>属性</p>
<ul>
<li>最小记录的<code>n_owned</code>值为<code>1</code>，这就代表着以最小记录结尾的这个分组中只有<code>1</code>条记录，也就是最小记录本身。</li>
<li>最大记录的<code>n_owned</code>值为<code>5</code>，这就代表着以最大记录结尾的这个分组中只有<code>5</code>条记录，包括最大记录本身还有我们自己插入的<code>4</code>条记录。</li>
</ul>
</li>
</ul>
<p><code>99</code>和<code>112</code>这样的地址偏移量很不直观，我们用箭头指向的方式替代数字，这样更易于我们理解，所以修改后的示意图就是这样：</p>
<p></p><figure><img alt="image_1couarh4no6j1a8q9htilr13qc2n.png-105.1kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c10dac72472?w=1032&amp;h=537&amp;f=png&amp;s=107616"><figcaption></figcaption></figure><p></p>
<p>哎呀，咋看上去怪怪的，这么乱的图对于我这个强迫症真是不能忍，那我们就暂时不管各条记录在存储设备上的排列方式了，单纯从<span style="color:red">逻辑上</span>看一下这些记录和页目录的关系：</p>
<p></p><figure><img alt="image_1couate3jr19gc18gl1cva1fcg34.png-100.8kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c10f2e61ad5?w=994&amp;h=550&amp;f=png&amp;s=103256"><figcaption></figcaption></figure><p></p>
<p>这样看就顺眼多了嘛！为什么最小记录的<code>n_owned</code>值为1，而最大记录的<code>n_owned</code>值为<code>5</code>呢，这里头有什么猫腻么？</p>
<p>是的，设计<code>InnoDB</code>的大叔们对每个分组中的记录条数是有规定的：<span style="color:red">对于最小记录所在的分组只能有 <em><strong>1</strong></em> 条记录，最大记录所在的分组拥有的记录条数只能在 <em><strong>1~8</strong></em> 条之间，剩下的分组中记录的条数范围只能在是 <em><strong>4~8</strong></em> 条之间</span>。所以分组是按照下边的步骤进行的：</p>
<ul>
<li>
<p>初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。</p>
</li>
<li>
<p>之后每插入一条记录，都会从<code>页目录</code>中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的<code>n_owned</code>值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8个。</p>
</li>
<li>
<p>在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在<code>页目录</code>中新增一个<code>槽</code>来记录这个新增分组中最大的那条记录的偏移量。</p>
</li>
</ul>
<p>由于现在<code>page_demo</code>表中的记录太少，无法演示添加了<code>页目录</code>之后加快查找速度的过程，所以再往<code>page_demo</code>表中添加一些记录：</p>
<pre><code class="hljs bash" lang="bash">mysql&gt; INSERT INTO page_demo VALUES(5, 500, <span class="hljs-string">'eeee'</span>), (6, 600, <span class="hljs-string">'ffff'</span>), (7, 700, <span class="hljs-string">'gggg'</span>), (8, 800, <span class="hljs-string">'hhhh'</span>), (9, 900, <span class="hljs-string">'iiii'</span>), (10, 1000, <span class="hljs-string">'jjjj'</span>), (11, 1100, <span class="hljs-string">'kkkk'</span>), (12, 1200, <span class="hljs-string">'llll'</span>), (13, 1300, <span class="hljs-string">'mmmm'</span>), (14, 1400, <span class="hljs-string">'nnnn'</span>), (15, 1500, <span class="hljs-string">'oooo'</span>), (16, 1600, <span class="hljs-string">'pppp'</span>);
Query OK, 12 rows affected (0.00 sec)
Records: 12  Duplicates: 0  Warnings: 0
</code></pre><p>哈，我们一口气又往表中添加了12条记录，现在页里边就一共有18条记录了（包括最小和最大记录），这些记录被分成了5个组，如图所示：</p>
<p></p><figure><img alt="image_1d6g64af2sgj1816ktl1q22dehp.png-189.1kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c10e3449897?w=1034&amp;h=638&amp;f=png&amp;s=193593"><figcaption></figcaption></figure><p></p>
<p>因为把16条记录的全部信息都画在一张图里太占地方，让人眼花缭乱的，所以只保留了用户记录头信息中的<code>n_owned</code>和<code>next_record</code>属性，也省略了各个记录之间的箭头，我没画不等于没有啊！现在看怎么从这个<code>页目录</code>中查找记录。因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用所谓的<code>二分法</code>来进行快速查找。4个槽的编号分别是：<code>0</code>、<code>1</code>、<code>2</code>、<code>3</code>、<code>4</code>，所以初始情况下最低的槽就是<code>low=0</code>，最高的槽就是<code>high=4</code>。比方说我们想找主键值为<code>6</code>的记录，过程是这样的：</p>
<ol>
<li>
<p>计算中间槽的位置：<code>(0+4)/2=2</code>，所以查看<code>槽2</code>对应记录的主键值为<code>8</code>，又因为<code>8 &gt; 6</code>，所以设置<code>high=2</code>，<code>low</code>保持不变。</p>
</li>
<li>
<p>重新计算中间槽的位置：<code>(0+2)/2=1</code>，所以查看<code>槽1</code>对应的主键值为<code>4</code>，又因为<code>4 &lt; 6</code>，所以设置<code>low=1</code>，<code>high</code>保持不变。</p>
</li>
<li>
<p>因为<code>high - low</code>的值为1，所以确定主键值为<code>6</code>的记录在<code>槽2</code>对应的组中。此刻我们需要找到<code>槽2</code>中主键值最小的那条记录，然后沿着单向链表遍历<code>槽2</code>中的记录。但是我们前边又说过，每个槽对应的记录都是该组中主键值最大的记录，这里<code>槽2</code>对应的记录是主键值为<code>8</code>的记录，怎么定位一个组中最小的记录呢？别忘了各个槽都是挨着的，我们可以很轻易的拿到<code>槽1</code>对应的记录（主键值为<code>4</code>），该条记录的下一条记录就是<code>槽2</code>中主键值最小的记录，该记录的主键值为<code>5</code>。所以我们可以从这条主键值为<code>5</code>的记录出发，遍历<code>槽2</code>中的各条记录，直到找到主键值为<code>6</code>的那条记录即可。由于一个组中包含的记录条数只能是1~8条，所以遍历一个组中的记录的代价是很小的。</p>
</li>
</ol>
<p>所以在一个数据页中查找指定主键值的记录的过程分为两步：</p>
<ol>
<li>
<p><span style="color:red">通过二分法确定该记录所在的槽，并找到该槽中主键值最小的那条记录</span>。</p>
</li>
<li>
<p><span style="color:red">通过记录的<code>next_record</code>属性遍历该槽所在的组中的各个记录</span>。</p>
</li>
</ol>
<blockquote class="warning"><p>小贴士：

如果你不知道二分法是个什么东西，找个基础算法书看看吧。什么？算法书写的看不懂？等我～
</p></blockquote><h2 class="heading">Page Header（页面头部）</h2>
<p>设计<code>InnoDB</code>的大叔们为了能得到一个数据页中存储的记录的状态信息，比如本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等，特意在页中定义了一个叫<code>Page Header</code>的部分，它是<code>页</code>结构的第二部分，这个部分占用固定的<code>56</code>个字节，专门存储各种状态信息，具体各个字节都是干嘛的看下表：</p>
<table>
<thead>
<tr>
<th style="text-align:center">名称</th>
<th style="text-align:center">占用空间大小</th>
<th style="text-align:center">描述</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"><code>PAGE_N_DIR_SLOTS</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">在页目录中的槽数量</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_HEAP_TOP</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">还未使用的空间最小地址，也就是说从该地址之后就是<code>Free Space</code></td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_N_HEAP</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">本页中的记录的数量（包括最小和最大记录以及标记为删除的记录）</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_FREE</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">第一个已经标记为删除的记录地址（各个已删除的记录通过<code>next_record</code>也会组成一个单链表，这个单链表中的记录可以被重新利用）</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_GARBAGE</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">已删除记录占用的字节数</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_LAST_INSERT</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">最后插入记录的位置</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_DIRECTION</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">记录插入的方向</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_N_DIRECTION</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">一个方向连续插入的记录数量</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_N_RECS</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">该页中记录的数量（不包括最小和最大记录以及被标记为删除的记录）</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_MAX_TRX_ID</code></td>
<td style="text-align:center"><code>8</code>字节</td>
<td style="text-align:center">修改当前页的最大事务ID，该值仅在二级索引中定义</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_LEVEL</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">当前页在B+树中所处的层级</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_INDEX_ID</code></td>
<td style="text-align:center"><code>8</code>字节</td>
<td style="text-align:center">索引ID，表示当前页属于哪个索引</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_BTR_SEG_LEAF</code></td>
<td style="text-align:center"><code>10</code>字节</td>
<td style="text-align:center">B+树叶子段的头部信息，仅在B+树的Root页定义</td>
</tr>
<tr>
<td style="text-align:center"><code>PAGE_BTR_SEG_TOP</code></td>
<td style="text-align:center"><code>10</code>字节</td>
<td style="text-align:center">B+树非叶子段的头部信息，仅在B+树的Root页定义</td>
</tr>
</tbody>
</table>
<p>如果大家认真看过前边的文章，从<code>PAGE_N_DIR_SLOTS</code>到<code>PAGE_LAST_INSERT</code>以及<code>PAGE_N_RECS</code>的意思大家一定是清楚的，如果不清楚，对不起，你应该回头再看一遍前边的文章。剩下的状态信息看不明白不要着急，饭要一口一口吃，东西要一点一点学（一定要稍安勿躁哦，不要被这些名词吓到）。在这里我们先唠叨一下<code>PAGE_DIRECTION</code>和<code>PAGE_N_DIRECTION</code>的意思：</p>
<ul>
<li>
<p><code>PAGE_DIRECTION</code></p>
<p>假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是<code>PAGE_DIRECTION</code>。</p>
</li>
<li>
<p><code>PAGE_N_DIRECTION</code></p>
<p>假设连续几次插入新记录的方向都是一致的，<code>InnoDB</code>会把沿着同一个方向插入记录的条数记下来，这个条数就用<code>PAGE_N_DIRECTION</code>这个状态表示。当然，如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计。</p>
</li>
</ul>
<p>至于我们没提到的那些属性，我没说是因为现在不需要大家知道。不要着急，当我们学完了后边的内容，你再回头看，一切都是那么清晰。</p>
<blockquote class="warning"><p>小贴士：

说到这个有些东西后边我们学过后回头看就很清晰的事儿不禁让我想到了乔布斯在斯坦福大学的演讲，摆一下原文：

“You can't connect the dots looking forward; you can only connect them looking backwards. So you have to trust that the dots will somehow connect in your future.You have to trust in something - your gut, destiny, life, karma, whatever. This approach has never let me down, and it has made all the difference in my life.”

上边这段话纯属心血来潮写的，大意是坚持做自己喜欢的事儿，你在做的时候可能并不能搞清楚这些事儿对自己之后的人生有啥影响，但当你一路走来回头看时，一切都是那么清晰，就像是命中注定的一样。上述内容跟MySQL毫无干系，请忽略～
</p></blockquote><h2 class="heading">File Header（文件头部）</h2>
<p>上边唠叨的<code>Page Header</code>是专门针对<code>数据页</code>记录的各种状态信息，比方说页里头有多少个记录了呀，有多少个槽了呀。我们现在描述的<code>File Header</code>针对各种类型的页都通用，也就是说不同类型的页都会以<code>File Header</code>作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁啦吧啦吧啦～ 这个部分占用固定的<code>38</code>个字节，是由下边这些内容组成的：</p>
<table>
<thead>
<tr>
<th style="text-align:center">名称</th>
<th style="text-align:center">占用空间大小</th>
<th style="text-align:center">描述</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"><code>FIL_PAGE_SPACE_OR_CHKSUM</code></td>
<td style="text-align:center"><code>4</code>字节</td>
<td style="text-align:center">页的校验和（checksum值）</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_OFFSET</code></td>
<td style="text-align:center"><code>4</code>字节</td>
<td style="text-align:center">页号</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_PREV</code></td>
<td style="text-align:center"><code>4</code>字节</td>
<td style="text-align:center">上一个页的页号</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_NEXT</code></td>
<td style="text-align:center"><code>4</code>字节</td>
<td style="text-align:center">下一个页的页号</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_LSN</code></td>
<td style="text-align:center"><code>8</code>字节</td>
<td style="text-align:center">页面被最后修改时对应的日志序列位置（英文名是：Log Sequence Number）</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE</code></td>
<td style="text-align:center"><code>2</code>字节</td>
<td style="text-align:center">该页的类型</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_FILE_FLUSH_LSN</code></td>
<td style="text-align:center"><code>8</code>字节</td>
<td style="text-align:center">仅在系统表空间的一个页中定义，代表文件至少被刷新到了对应的LSN值</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID</code></td>
<td style="text-align:center"><code>4</code>字节</td>
<td style="text-align:center">页属于哪个表空间</td>
</tr>
</tbody>
</table>
<p>对照着这个表格，我们看几个目前比较重要的部分：</p>
<ul>
<li>
<p><code>FIL_PAGE_SPACE_OR_CHKSUM</code></p>
<p>这个代表当前页面的校验和（checksum）。啥是个校验和？就是对于一个很长很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为<code>校验和</code>。这样在比较两个很长的字节串之前先比较这两个长字节串的校验和，如果校验和都不一样两个长字节串肯定是不同的，所以省去了直接比较两个比较长的字节串的时间损耗。</p>
</li>
<li>
<p><code>FIL_PAGE_OFFSET</code></p>
<p>每一个<code>页</code>都有一个单独的页号，就跟你的身份证号码一样，<code>InnoDB</code>通过页号来可以唯一定位一个<code>页</code>。</p>
</li>
<li>
<p><code>FIL_PAGE_TYPE</code></p>
<p>这个代表当前<code>页</code>的类型，我们前边说过，<code>InnoDB</code>为了不同的目的而把页分为不同的类型，我们上边介绍的其实都是存储记录的<code>数据页</code>，其实还有很多别的类型的页，具体如下表：</p>
<table>
<thead>
<tr>
<th style="text-align:center">类型名称</th>
<th style="text-align:center">十六进制</th>
<th style="text-align:center">描述</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE_ALLOCATED</code></td>
<td style="text-align:center">0x0000</td>
<td style="text-align:center">最新分配，还没使用</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_UNDO_LOG</code></td>
<td style="text-align:center">0x0002</td>
<td style="text-align:center">Undo日志页</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_INODE</code></td>
<td style="text-align:center">0x0003</td>
<td style="text-align:center">段信息节点</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_IBUF_FREE_LIST</code></td>
<td style="text-align:center">0x0004</td>
<td style="text-align:center">Insert Buffer空闲列表</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_IBUF_BITMAP</code></td>
<td style="text-align:center">0x0005</td>
<td style="text-align:center">Insert Buffer位图</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE_SYS</code></td>
<td style="text-align:center">0x0006</td>
<td style="text-align:center">系统页</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE_TRX_SYS</code></td>
<td style="text-align:center">0x0007</td>
<td style="text-align:center">事务系统数据</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE_FSP_HDR</code></td>
<td style="text-align:center">0x0008</td>
<td style="text-align:center">表空间头部信息</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE_XDES</code></td>
<td style="text-align:center">0x0009</td>
<td style="text-align:center">扩展描述页</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_TYPE_BLOB</code></td>
<td style="text-align:center">0x000A</td>
<td style="text-align:center">BLOB页</td>
</tr>
<tr>
<td style="text-align:center"><code>FIL_PAGE_INDEX</code></td>
<td style="text-align:center">0x45BF</td>
<td style="text-align:center">索引页，也就是我们所说的<code>数据页</code></td>
</tr>
</tbody>
</table>
<p>我们存放记录的数据页的类型其实是<code>FIL_PAGE_INDEX</code>，也就是所谓的<code>索引页</code>。至于啥是个索引，且听下回分解～</p>
</li>
<li>
<p><code>FIL_PAGE_PREV</code>和<code>FIL_PAGE_NEXT</code></p>
<p>我们前边强调过，<code>InnoDB</code>都是以页为单位存放数据的，有时候我们存放某种类型的数据占用的空间非常大（比方说一张表中可以有成千上万条记录），<code>InnoDB</code>可能不可以一次性为这么多数据分配一个非常大的存储空间，如果分散到多个不连续的页中存储的话需要把这些页关联起来，<code>FIL_PAGE_PREV</code>和<code>FIL_PAGE_NEXT</code>就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了，而无需这些页在物理上真正连着。需要注意的是，<span style="color:red">并不是所有类型的页都有上一个和下一个页的属性</span>，不过我们本集中唠叨的<code>数据页</code>（也就是类型为<code>FIL_PAGE_INDEX</code>的页）是有这两个属性的，所以所有的数据页其实是一个双链表，就像这样：</p>
<p></p><figure><img alt="image_1ca00fhg418pl1f1a1iav1uo3aou9.png-90.9kB" src="https://user-gold-cdn.xitu.io/2019/5/8/16a95c10eb9d61ce?w=898&amp;h=365&amp;f=png&amp;s=93102"><figcaption></figcaption></figure><p></p>
</li>
</ul>
<p>关于<code>File Header</code>的其他属性我们暂时用不到，等用到的时候再提哈～</p>
<h2 class="heading">File Trailer</h2>
<p>我们知道<code>InnoDB</code>存储引擎会把数据存储到磁盘上，但是磁盘速度太慢，需要以<code>页</code>为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据<span style="color:red">同步</span>到磁盘中。但是在同步了一半的时候中断电了咋办，这不是莫名尴尬么？为了检测一个页是否完整（也就是在同步的时候有没有发生只同步一半的尴尬情况），设计<code>InnoDB</code>的大叔们在每个页的尾部都加了一个<code>File Trailer</code>部分，这个部分由<code>8</code>个字节组成，可以分成2个小部分：</p>
<ul>
<li>
<p>前4个字节代表页的校验和</p>
<p>这个部分是和<code>File Header</code>中的校验和相对应的。每当一个页面在内存中修改了，在同步之前就要把它的校验和算出来，因为<code>File Header</code>在页面的前边，所以校验和会被首先同步到磁盘，当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的首部和尾部的校验和应该是一致的。如果写了一半儿断电了，那么在<code>File Header</code>中的校验和就代表着已经修改过的页，而在<code>File Trialer</code>中的校验和代表着原先的页，二者不同则意味着同步中间出了错。</p>
</li>
<li>
<p>后4个字节代表页面被最后修改时对应的日志序列位置（LSN）</p>
<p>这个部分也是为了校验页的完整性的，只不过我们目前还没说<code>LSN</code>是个什么意思，所以大家可以先不用管这个属性。</p>
</li>
</ul>
<p>这个<code>File Trailer</code>与<code>File Header</code>类似，都是所有类型的页通用的。</p>
<h2 class="heading">总结</h2>
<ol>
<li>
<p>InnoDB为了不同的目的而设计了不同类型的页，我们把用于存放记录的页叫做<code>数据页</code>。</p>
</li>
<li>
<p>一个数据页可以被大致划分为7个部分，分别是</p>
<ul>
<li><code>File Header</code>，表示页的一些通用信息，占固定的38字节。</li>
<li><code>Page Header</code>，表示数据页专有的一些信息，占固定的56个字节。</li>
<li><code>Infimum + Supremum</code>，两个虚拟的伪记录，分别表示页中的最小和最大记录，占固定的<code>26</code>个字节。</li>
<li><code>User Records</code>：真实存储我们插入的记录的部分，大小不固定。</li>
<li><code>Free Space</code>：页中尚未使用的部分，大小不确定。</li>
<li><code>Page Directory</code>：页中的某些记录相对位置，也就是各个槽在页面中的地址偏移量，大小不固定，插入的记录越多，这个部分占用的空间越多。</li>
<li><code>File Trailer</code>：用于检验页是否完整的部分，占用固定的8个字节。</li>
</ul>
</li>
<li>
<p>每个记录的头信息中都有一个<code>next_record</code>属性，从而使页中的所有记录串联成一个<code>单链表</code>。</p>
</li>
<li>
<p><code>InnoDB</code>会为把页中的记录划分为若干个组，每个组的最后一个记录的地址偏移量作为一个<code>槽</code>，存放在<code>Page Directory</code>中，所以在一个页中根据主键查找记录是非常快的，分为两步：</p>
<ul>
<li>
<p>通过二分法确定该记录所在的槽。</p>
</li>
<li>
<p>通过记录的next_record属性遍历该槽所在的组中的各个记录。</p>
</li>
</ul>
</li>
<li>
<p>每个数据页的<code>File Header</code>部分都有上一个和下一个页的编号，所以所有的数据页会组成一个<code>双链表</code>。</p>
</li>
<li>
<p>为保证从内存中同步到磁盘的页的完整性，在页的首部和尾部都会存储页中数据的校验和和页面最后修改时对应的<code>LSN</code>值，如果首部和尾部的校验和和<code>LSN</code>值校验不成功的话，就说明同步过程出现了问题。</p>
</li>
</ol>
